#include <iostream>
using namespace std;
#include <glog/logging.h>
#include <time.h>

int recursion_liner_sum(int A[], int n);
void test_recursion_liner_sum(char** argv);

void reverse(int *A, int low, int high);
void test_reverse(char **argv);

int64_t power2(int n);
int64_t power2_improve(int n);
void test_power2(char** argv);

int64_t fibonacci_recursion(int n);
int64_t fibonacci_dynamic(int n);
void test_fibonacci(char ** argv);

int main(int argc, char** argv)
{
    google::InitGoogleLogging(argv[0]);
    google::SetLogDestination(google::INFO, "../log/");
    FLAGS_stderrthreshold = google::INFO;
    LOG(INFO)<< "Hello data structure!" << endl;

    //test_recursion_liner_sum(argv);
    //test_reverse(argv);
    //test_power2(argv);
    test_fibonacci(argv);
    return 0;
}


/**
 * @brief recursion_liner_sum
 * @param A
 * @param n : the length of A
 */
int recursion_liner_sum(int A[], int n)
{
    LOG(INFO)<< "Hello: recursion_liner_sum" << endl;

    if(n == 0)
        return 0;
    else
        return ( A[n-1]+recursion_liner_sum(A, n-1) );
}
/**
 * @brief test_recursion_liner_sum
 * @param A
 * @param n
 */
void test_recursion_liner_sum(char** argv)
{
    int A[] = {1, 2, 3, 4, 5};
    int sum=recursion_liner_sum(A, 5);
    cout << "sum = " << sum << endl;
}
/**
 * @brief reverse
 * @param A
 * @param low
 * @param high
 */
void reverse(int *A, int low, int high)
{
    if(low < high)
    {
        swap(A[low], A[high]);
        reverse(A, low+1, high-1);
    }
}
/**
 * @brief test_reverse
 * @param argv
 */
void test_reverse(char **argv)
{
    int A[] = {1, 2, 3, 4, 5};
    reverse(A, 0, 4);
    for(int i = 0; i < 5; ++i)
    {
        cout << A[i] << " ";
    }
    cout << endl;
}

int64_t power2(int n)
{
    if( n ==0 )
        return 1;
    else
        return 2*power2(n-1);
}
int64_t power2_improve(int n)
{
    if(n == 0)
        return 1;
    else if (n % 2 == 0)
        return ( power2_improve( int(n/2) ) * power2_improve( int(n/2) ) );
    else if(n % 2 == 1)
        return ( power2_improve( int(n/2) ) * power2_improve( int(n/2) ) *2 );
}
void test_power2(char** argv)
{
    int n = 60;     //power2(80) over
    clock_t startTime, endTime;
    double durationTime;
    int64_t value;

    startTime = clock();
    value = power2(n);
    endTime = clock();
    durationTime = (double) (endTime - startTime) / CLOCKS_PER_SEC;
    cout << "The time use of power2() = " << durationTime << endl;
    cout << "The value of power2(n) = " << value << endl;


    startTime = clock();
    value = power2_improve(n);
    endTime = clock();
    durationTime = (double) (endTime - startTime) / CLOCKS_PER_SEC;
    cout << "The time use of power2() = " << durationTime << endl;
    cout << "The value of power2_improve(n) = " << value << endl;
}

int64_t fibonacci_recursion(int n)
{
    int64_t value;
    if( n <= 1)
        return 1;
    else
    {
        value = fibonacci_recursion(n-2) + fibonacci_recursion(n-1);
        return value;
    }
}
int64_t fibonacci_dynamic(int n)
{
    int pre = 1, now = 1;
    n = n-2;
    while( n > 0 )
    {
        now = pre + now;
        pre = now - pre;
        n--;
    }
    return now;
}

void test_fibonacci(char ** argv)
{
    int n = 4;     //n = 45 uses 8seconds
    clock_t startTime, endTime;
    double durationTime;
    int64_t value;

//    startTime = clock();
//    value  = fibonacci_recursion(n);
//    endTime = clock();
//    durationTime = (double) (endTime - startTime) / CLOCKS_PER_SEC;
//    cout << "value = " << value << endl;
//    cout << "The time use of fibonacci_recursion(n) = " << durationTime << endl;

    startTime = clock();
    value  = fibonacci_dynamic(n);
    endTime = clock();
    durationTime = (double) (endTime - startTime) / CLOCKS_PER_SEC;
    cout << "value = " << value << endl;
    cout << "The time use of fibonacci_recursion(n) = " << durationTime << endl;
}
